﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#define ll __int64
#define N 46

int main()
{
    int i, j;
    ll c[N][N];
    for (i = 1; i < N; i++)
        c[i][0] = c[i][i] = 1;
    for (i = 2; i < N; i++)
        for (j = 1; j < i; j++)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]);


    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        ll y = 0;
        for (i = 0; i <= n / 2; i++)
        {
            y += c[n][i] * c[n - i][i];
        }
        printf("%I64d\n", y);


    }
    return 0;
}
/*
题目描述
一个n列的网格，从(0,0)网格点出发，波形存在平波(从(x,y)到(x+1,y))，上升波(从(x,y)到(x+1,y+1))，下降波(从(x,y)到(x+1,y−1))三种波形，
请问从(0,0)出发，最终到达(n,0)的不同波形有多少种？



输入
第一行是样例数T(1≤T≤42)。 以后每行一个整数n(1≤n≤42)。

输出
每行输出一个样例的结果。

样例输入
3
1
2
3
样例输出
1
3
7
*/